public class MultiplyStrings {
    // 纯模拟列竖式
    public String multiply(String num1, String num2) {
        // 细节二: 特判一下多出 0 的情况
        if (num2.length() == 1 && num2.charAt(0) == '0' || num1.length() == 1 && num1.charAt(0) == '0') {
            return "0";
        }
        // 逆序数组
        String num1Reverse = new StringBuilder(num1).reverse().toString();
        StringBuilder ret = new StringBuilder();

        int n = num2.length();
        for (int i = 0; i < n; i++) {
            // 用 tmp 存储每位相乘的结果
            StringBuilder tmp = new StringBuilder();
            // 这里我并没有逆序第二个数组, 但想拿到较小位, n-i-1 即可, 哪种方式都可以
            // 固定第二个数组的元素
            int fixed = num2.charAt(n - i - 1) - '0';
            int t = 0;
            // 细节一: 处理高位零
            int zero = i;
            while(zero != 0) {
                tmp.append('0');
                zero--;
            }
            for (int j = 0; j < num1.length(); j++) {
                // 遍历第一个数组元素, 依次与 fixed 相乘
                int multiplier = num1Reverse.charAt(j) - '0';
                t += fixed * multiplier;
                tmp.append((char) (t % 10 + '0'));
                t /= 10;
            }
            if (t != 0) {
                tmp.append((char) (t % 10 + '0'));
            }
            ret = add(tmp, ret);
        }
        return ret.reverse().toString();
    }

    public StringBuilder add(StringBuilder tmp, StringBuilder ret) {
        // tmp 和 ret 的高精度相加运算
        StringBuilder str = new StringBuilder();
        int tmpLen = tmp.length(), retLen = ret.length();
        int cur1 = 0, cur2 = 0;
        int t = 0;
        while(cur1 < tmpLen || cur2 < retLen || t != 0) {
            if(cur1 < tmpLen) {
                t += tmp.charAt(cur1) - '0';
                cur1++;
            }
            if(cur2 < retLen) {
                t += ret.charAt(cur2) - '0';
                cur2++;
            }

            str.append((char)(t % 10 + '0'));
            t /= 10;
        }
        return str;
    }

    // 对解法一的优化: 无进位相乘然后相加, 最后处理进位
    public String multiply1(String num1, String num2) {
        if (num2.length() == 1 && num2.charAt(0) == '0' || num1.length() == 1 && num1.charAt(0) == '0') {
            return "0";
        }
        String num1Reverse = new StringBuilder(num1).reverse().toString();
        StringBuilder ret = new StringBuilder();

        int n = num1.length();
        int m = num2.length();
        int[] tmp = new int[n + m - 1];
        for (int i = 0; i < m; i++) {
            int fixed = num2.charAt(m - i - 1) - '0';
            for (int j = 0; j < n; j++) {
                int multiplier = num1Reverse.charAt(j) - '0';
                tmp[i + j] += fixed * multiplier;
            }
        }
        ret = carry(tmp, ret);
        return ret.toString();
    }

    public StringBuilder carry(int[] tmp, StringBuilder ret) {
        // 处理进位
        StringBuilder str = new StringBuilder();
        int t = 0;
        for(int i = 0; i < tmp.length; i++) {
            t += tmp[i];
            str.append((char)(t % 10 + '0'));
            t /= 10;
        }
        if(t != 0) {
            str.append((char)(t % 10 + '0'));
        }
        return str.reverse();
    }
}
